package com.li.algorithm.leetcode.hot100;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;


public class Test32 {
    /**
     * 方法1:迭代+映射
     *
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)
     */
//    public Node copyRandomList(Node head) {
//        if (head == null) {
//            return null;
//        }
//        //从头节点开始
//        //复制当前节点
//        //复制next节点
//        //进入next节点，依次迭代
//        //将上述顺序节点放入array数组，后续遍历random时方便获取
//        //进行第二次遍历。遍历复制后第节点，同时遍历原节点，在新节点中指定random
//        //新增map，将原链表节点与新链表节点建立一一对应关系
//        HashMap<Node, Node> map = new HashMap<>();
//        Node p = head;
//        Node qHead = new Node(head.val);
//        Node q = qHead;
//        map.put(head, qHead);
//        while (p.next != null) {
//            Node nextQ = new Node(p.next.val);
//            q.next = nextQ;
//            map.put(p.next, nextQ);
//            q = nextQ;
//            p = p.next;
//        }
//        p = head;
//        q = qHead;
//        while (p != null) {
//            q.random = map.get(p.random);
//            p = p.next;
//            q = q.next;
//        }
//        return qHead;
//    }

    /**
     * 方法2:递归
     * 遍历该链表的过程中，我们检查「当前节点的后继节点」和「当前节点的随机指针指向的节点」的创建情况。
     * 如果这两个节点中的任何一个节点的新节点没有被创建，我们都立刻递归地进行创建。
     * 当我们拷贝完成，回溯到当前层时，我们即可完成当前节点的指针赋值。
     *
     * 注意一个节点可能被多个其他节点指向，因此我们可能递归地多次尝试拷贝某个节点，为了防止重复拷贝，我们用哈希表记录每一个节点对应新节点的创建情况
     */
//    Map<Node, Node> map = new HashMap<>();
//    public Node copyRandomList(Node head) {
//        if (head == null) {
//            return null;
//        }
//        if (map.containsKey(head)) {
//            Node newHead = new Node(head.val);
//            map.put(head, newHead);
//            newHead.next = copyRandomList(head.next);
//            newHead.random = copyRandomList(head.random);
//        }
//        return map.get(head);
//    }

    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        //第一步：将新节点穿插到旧节点到后面
        for (Node node = head; node != null; node = node.next.next) {
            Node nodeNew = new Node(node.val);
            nodeNew.next = node.next;
            node.next = nodeNew;
        }
        //第二步：复制旧节点到random节点（新节点始终在旧节点的next）
        for (Node node = head; node != null; node = node.next.next) {
            Node nodeNew = node.next;
            nodeNew.random = node.random != null ? node.random.next : null;
        }
        Node headNew = head.next;
        //第三步：恢复旧链表与新链表
        for (Node node = head; node != null; node = node.next) {
            Node nodeNew = node.next;
            node.next = node.next.next;
            nodeNew.next = nodeNew.next != null ? nodeNew.next.next : null;
        }
        return headNew;
    }


    public static void main(String[] args) {
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        Node n4 = new Node(4);
        Node n5 = new Node(5);
        n1.next = n2;n1.random = null;
        n2.next = n3;n2.random = n1;
        n3.next = n4;n3.random = n5;
        n4.next = n5;n4.random = n3;
        n5.random = n1;
        Node result = new Test32().copyRandomList(n1);
        while (result != null) {
            Integer random = result.random == null ? null : result.random.val;
            System.out.println(result.val + " " + random);
            result = result.next;
        }
    }
}
